package org.leetcode.medium;

import org.junit.Test;
import org.leetcode.utils.TreeNode;

import java.util.ArrayList;

/**
 * 验证二叉搜索树
 * 要点：二叉搜索树的中序遍历是严格递增的
 * @author walnker
 *
 */
public class IsValidBST {
    public boolean isValidBST(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> list1 = inOrderTraverse(root, list);
        for (int i = 0; i < list1.size() - 1; i++) {
            if (list.get(i) >= list.get(i + 1)) {
                return false;
            }
        }
        return true;
    }

    // 失败
    public boolean isValidBST(TreeNode root, int y, int val) {
        if (root == null) {
            return true;
        }
        if ((y == 0 && root.val == val) || (y == 1 && root.val < val) || (y == 2 && root.val > val)) {
            y = 1;
            if (isValidBST(root.left, y, root.val)) ;
            else {
                return false;
            }
            y = 2;
            if (isValidBST(root.right, y, root.val)) ;
            else {
                return false;
            }
        } else {
            return false;
        }
        return true;
    }


    // 失败
    public boolean isValidBST2(TreeNode root) {
        return isValidBST3(root, root);

    }

    // 失败
    public boolean isValidBST3(TreeNode root, TreeNode cur) {
        if (root == null) {
            return true;
        }
        if (BSTSearch(cur, root.val)) {
            if (isValidBST3(root.left, cur)) ;
            else {
                return false;
            }
            if (isValidBST3(root.right, cur)) ;
            else {
                return false;
            }
        } else {
            return false;
        }
        return true;
    }

    //二叉搜索树查找
    public boolean BSTSearch(TreeNode root, int val) {
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        }
        if (val < root.val) {
            return BSTSearch(root.left, val);
        } else {
            return BSTSearch(root.right, val);
        }
    }

    // 二叉搜索树插入
    public boolean BSTInsert(TreeNode root, int val) {
        TreeNode newNode = new TreeNode(val);
        if (root == null) {
            root = newNode;
            return true;
        }
        if (val == root.val) {
            return false;
        } else if (val < root.val) {
            return BSTInsert(root.left, val);
        } else {
            return BSTInsert(root.right, val);
        }
    }

    // 验证二叉搜索树创建是否正确, 如果成功创建，则进行中序遍历必定是严格递增的
    public ArrayList<Integer> inOrderTraverse(TreeNode root, ArrayList<Integer> list) {
        if (root == null) {
            return null;
        }
        inOrderTraverse(root.left, list);
        list.add(root.val);
        inOrderTraverse(root.right, list);
        return list;

    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(2,
                new TreeNode(1), new TreeNode(3));
        System.out.println(isValidBST(root));
    }
}
